An image typically shows variation of a value or a combination of values over a 2D array. An image can be a regular color picture taken by a camera, an X-ray picture, an infrared picture, an ultrasound picture, etc. There are few reported efficient and systematic way to search an image (e.g., a human face) that includes a specific sub-image of interest (e.g., an eye) embedded in the image, which is stored in a stack of images (e.g., various pictures).
The image search system is used to find an image or images that contain a specific pattern. For example, a user may inquire what maps (images) contain a specific landmark such as the Golden Gate bridge. The query (sub-image) may be in the form of a picture of the Golden Gate bridge. The image document search system will output a number of maps (images) that contain picture of the Golden Gate bridge.
In another example, a collection of millions of satellite pictures are provided. A picture is then randomly picked up from the collection. The picture is cut into pieces. A piece of the picture is used as a reference (sub-image) or a query. The image search system will be able to find the original picture (image) to which the piece belongs, in a collection of millions pictures, and locate the position of that piece in the found picture (image).
To the inventor's knowledge, all 2D image search methods are based on a 2D matching operation, which may be a kin to the 2D correlation. If the size of sub-image is (m×n), and the size of image is (M×N), to complete a 2D matching operation between an image and a sub-image, it may take approximately (M×N)×(m×n) steps of computations. To match thousands of images, thousands of (M×N)×(m×n) steps of computations are needed. Accordingly, methods for 2D matching requiring less steps of computations are desired. Methods for searching 2D image that includes a sub-image requiring less steps of computations are desired as well.
Corresponding reference characters indicate corresponding components throughout the several views of the drawings. Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of various embodiments of the present invention.